首页 > 试题广场 >

括号匹配深度

[编程题]括号匹配深度

热度指数：2429 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

一个合法的括号匹配序列有以下定义:
1、空串""是一个合法的括号匹配序列
2、如果"X"和"Y"都是合法的括号匹配序列,"XY"也是一个合法的括号匹配序列
3、如果"X"是一个合法的括号匹配序列,那么"(X)"也是一个合法的括号匹配序列
4、每个合法的括号序列都可以由以上规则生成。
例如: "","()","()()","((()))"都是合法的括号序列
对于一个合法的括号序列我们又有以下定义它的深度:
1、空串""的深度是0
2、如果字符串"X"的深度是x,字符串"Y"的深度是y,那么字符串"XY"的深度为max(x,y) 3、如果"X"的深度是x,那么字符串"(X)"的深度是x+1
例如: "()()()"的深度是1,"((()))"的深度是3。牛牛现在给你一个合法的括号序列,需要你计算出其深度。

输入描述:

输入包括一个合法的括号序列s,s长度length(2 ≤ length ≤ 50),序列中只包含'('和')'。

输出描述:

输出一个正整数,即这个序列的深度。

示例1

输入

(())

输出

算法知识视频讲解

Python 3

牛客988422122号

list_1,list_2 = [],[]
str_1 = input()
for i in str_1:
    if i == ")":
        list_1.append(i)
        if len(list_1)>len(list_2):
            list_2 = list_1
    else:
        list_1 = []
str_2 = "".join(str_1)
str_3 = "".join(list_2)
int_1 = str_2.index(str_3) + len(str_3)
print(len(str_3) + str_2[int_1:].count(")") - str_2[int_1:].count("("))

python新手，有大佬看看写的对不对

发表于 2022-03-31 21:29:44 回复(0)

Python 3

牛客260097117号

rec = []
depth = 0

string = input()
for i in string:
    if i == '(':
        depth += 1
    elif i == ')':
        rec.append(depth)
        depth -= 1
if depth == 0:
    print(max(rec))

这个方法比较慢，不用确认输入是否正确应该可以有简洁方法

发表于 2021-12-01 01:43:38 回复(0)

Python 3

scionx

if __name__ == '__main__':
    while True:
        try:
            s = input()
            stack = max_depth = 0
            for i in s:
                if i == '(':
                    stack += 1
                    max_depth = max(max_depth, stack)
                else:
                    stack -= 1
            print(max_depth)
        except:
            break

发表于 2021-08-06 11:09:50 回复(0)